Herramientas de Optimización

Jorge Ivan Romero

Doctorado en Ingeniería

14/08/2021

Que es optimización?

La optimización es un tema importante con un amplio campo de aplicaciones en los problemas de toma de decisiones que surgen en economía, ingeniería, logística y transporte, planificación del tráfico, ubicación y diseño de instalaciones, telecomunicaciones, redes sociales y biológicas, aprendizaje automático y otros campos.

\begin{itemize} \item El primer problema de optimización formal de la historia se estableció formalmente en el 300 aC, en: \textbf{ Elementos de geometría de Euclides , Libro VI}, y se ocupa de la identificación de un punto en el lado de un triángulo de modo que el paralelogramo resultante, obtenido al trazar las líneas paralelas a los otros dos lados del triángulo desde este punto, tiene un área máxima. \item También otro matemático griego antiguo, Heron (100 aC), quien resolvió otro problema de optimización en geometría, encontrar un punto en una línea dada tal que la suma de las distancias de otros dos puntos dados sea mínima. \end{itemize}

Linea de tiempo

\begin{itemize} \item 1947 & \textbf{Dantzing} Método simplex. \item 1950-1956 & \textbf{Kun-Tucker} Programacion No Lineal. \item 1953 & \textbf{Kendall} Notación sistemas de colas. \item 1954 & \textbf{Lemke} Simplex Dual. \item 1958 & \textbf{Bellman} Programación dinámica. \item 1958 & \textbf{Gomory} Programación entera. \item 1958 & \textbf{Arrow-Karlin} Inventarios. \item 1959 & \textbf{Dijkstra} Algoritmo de ruta mas corta. \item 1956-1962 & \textbf{Ford-Fulkerson} Redes de flujo. \item 1960 & \textbf{Raiffa} Análisis de decisiones. \item 1960 & \textbf{Land y Doig} Algoritmo de ramificación y acotamiento. \item 1961 & \textbf{Little} Formula de little para lineas de espera. \item 1962 & \textbf{Ford-Fulkerson} Método primal dual. \item 1984 & \textbf{Hopfiel} Red Neuronal. \item 1984 & \textbf{Holland} Algoritmos genéticos. \item 1984 & \textbf{Saaty} PAJ. \item 1986 & \textbf{Hopfield y Tank} Redes neuronales en IO. \item 1986 & \textbf{Glover} Busqueda Tabu. \item 1989-1992 & \textbf{Lee} Cadena de suministro. \item 1989-1995 & \textbf{Englewood} Colas, Inventarios y redes. \item 1996 & \textbf{Fishman} Monte carlo, conceptos, algoritmos y aplicaciones. \item 1999 & \textbf{Hammond, Kenney y Raifa} Decisiones inteligentes. \item 2003 & \textbf{Schrijver} Optimizacion combinatoria- aportes. \end{itemize}

Tiempo de solución

Si bien se han desarrollado algunos algoritmos de solución para los problemas de optimización más interesantes, y aunque se han propuesto varios enfoques de solución diferentes para los mismos problemas de optimización, es posible que su rendimiento no siempre sea satisfactorio en la práctica y / o en la teoría.

Tematicas de curso

\begin{itemize} \item Técnicas de optimización clásicas \item Tecnicas heuristicas y metaheuristicas clasicas(algoritmos de busqueda y recorrido) \item Tecnicas metaheuristicas (busqueda tabu, recocido simulado, algoritmos geneticos) \item Algoritmos bio inspirados (colonia de hormigas, enjambre de particulas) \end{itemize}

Técnicas de optimización clásicas

Programación Lineal

import plotly.graph_objects as go

fig = go.Figure(data=[
    go.Mesh3d(
        x=[0, 1, 2, 0],
        y=[0, 0, 1, 2],
        z=[0, 2, 0, 1],
        colorbar_title='z',
        colorscale=[[0, 'gold'],
                    [0.5, 'mediumturquoise'],
                    [1, 'magenta']],
        # Intensity of each vertex, which will be interpolated and color-coded
        intensity=[0, 0.33, 0.66, 1],
        # i, j and k give the vertices of triangles
        # here we represent the 4 triangles of the tetrahedron surface
        i=[0, 0, 0, 1],
        j=[1, 2, 3, 2],
        k=[2, 3, 1, 3],
        name='y',
        showscale=True
    )
])
fig.update_layout(title='En lp tenemos vertices lineales', autosize=False,
                  width=500, height=500,
                  margin=dict(l=65, r=50, b=65, t=90))

fig.show()

Programacion no lineal

import plotly.graph_objects as go

import pandas as pd

# Read data from a csv
z_data = pd.read_csv('https://raw.githubusercontent.com/plotly/datasets/master/api_docs/mt_bruno_elevation.csv')

fig = go.Figure(data=[go.Surface(z=z_data.values)])

fig.update_layout(title='En nlp cambia: Superficies con multiples vertices', autosize=False,
                  width=500, height=500,
                  margin=dict(l=65, r=50, b=65, t=90))

fig.show()

Que hay de la metaheuristica?

Los enfoques heurísticos y metaheurísticos modernos (del griego “Heuriskein” -'υρισ κ ιν - encontrar, descubrir) se han vuelto tan populares que ha nacido una nueva rama de optimización que diseña algoritmos inspirados en la física o la naturaleza, como optimización simulada de recocido, colonia de hormigas o enjambre de partículas.

Que herramientas vamos a utilizar?

Comencemos con un problema lineal simple en OR Tools

Instalemos OR Tools con el comando PIP

pip install ortools

Nuestro problema es:

basico para resolver un problema de PL:

\begin{enumerate} \item Importe el contenedor del solucionador lineal, \item declarar el solucionador de LP, \item definir las variables, \item definir las restricciones, \item definir el objetivo, \itemllamar al solucionador de LP; y mostrar la solución \end{enumerate}

from ortools.linear_solver import pywraplp

def EjemploPL():
    """Linear programming sample."""
    # Agregar el solver GLOP al problema
    solver = pywraplp.Solver.CreateSolver('CBC')

    # Crear las dos variables x1 y x2 >= a cero, osea positivas.
    x1 = solver.NumVar(0, solver.infinity(), 'x1')
    x2 = solver.NumVar(0, solver.infinity(), 'x2')

    print('Numero de variables =', solver.NumVariables())
    print('R1 = x2+2x2<=14')
    # Constraint 0: x + 2y <= 14.
    solver.Add(x1 + 2 * x2 <= 14.0)

    # Constraint 1: 3x - y >= 0.
    solver.Add(3 * x1 - x2 >= 0.0)

    # Constraint 2: x - y <= 2.
    solver.Add(x1 - x2 <= 2.0)

    print('Numero de restricciones =', solver.NumConstraints())

    # Objective function: 3x + 4y.
    solver.Maximize(3 * x1 + 4 * x2)

    # Solve the system.
    status = solver.Solve()
  

    if status == pywraplp.Solver.OPTIMAL:
        print('Solucion:')
        print('Z =', solver.Objective().Value())
        print('x1 =', x1.solution_value())
        print('x2 =', x2.solution_value())
    else:
        print('Grave!, el problema no tiene solucion.')

    print('\nAvanzado:')
    print('Problem solved in %f milliseconds' % solver.wall_time())
    print('Problem solved in %d iterations' % solver.iterations())


EjemploPL()

Numero de variables = 2
R1 = x2+2x2<=14
Numero de restricciones = 3
Solucion:
Z = 34.0
x1 = 6.0
x2 = 4.0

Avanzado:
Problem solved in 23.000000 milliseconds
Problem solved in 0 iterations

Gracias por su atención